/*
 * TwoWay.cpp
 *
 *  Created on: 02-09-2013
 *      Author: Krzychu
 */

#include "TwoWay.h"

#include "../Structures/Config.h"

#include <stdio.h>
#include <string.h>

#define MAX(a, b) (a > b) ? a : b
#define ASIZE 255

TwoWay::TwoWay()
{

}

TwoWay::~TwoWay()
{

}

std::string TwoWay::getName()
{
	return "Two Way";
}

/* Computing of the maximal suffix for <= */
int maxSuf(std::string pattern, int *p)
{
	int patternSize = pattern.size();

	int ms, j, k;
	char a, b;

	ms = -1;
	j = 0;
	k = *p = 1;
	while (j + k < patternSize)
	{
		a = pattern[j + k];
		b = pattern[ms + k];
		if (a < b)
		{
			j += k;
			k = 1;
			*p = j - ms;
		}
		else if (a == b)
			if (k != *p)
				++k;
			else
			{
				j += *p;
				k = 1;
			}
		else
		{ /* a > b */
			ms = j;
			j = ms + 1;
			k = *p = 1;
		}
	}
	return (ms);
}

/* Computing of the maximal suffix for >= */
int maxSufTilde(std::string pattern, int *p)
{
	int patternSize = pattern.size();

	int ms, j, k;
	char a, b;

	ms = -1;
	j = 0;
	k = *p = 1;
	while (j + k < patternSize)
	{
		a = pattern[j + k];
		b = pattern[ms + k];
		if (a > b)
		{
			j += k;
			k = 1;
			*p = j - ms;
		}
		else if (a == b)
		{
			if (k != *p)
			{
				++k;
			}
			else
			{
				j += *p;
				k = 1;
			}
		}
		else
		{ /* a < b */
			ms = j;
			j = ms + 1;
			k = *p = 1;
		}
	}
	return (ms);
}

searchResult TwoWay::execute(std::string text, std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	const char* patternChar = pattern.c_str();

	int i, j, ell, memory, p, per, q;

	/* Preprocessing */
	i = maxSuf(pattern, &p);
	j = maxSufTilde(pattern, &q);
	if (i > j)
	{
		ell = i;
		per = p;
	}
	else
	{
		ell = j;
		per = q;
	}

	/* Searching */
	if (memcmp(patternChar, patternChar + per, ell + 1) == 0)
	{
		j = 0;
		memory = -1;
		while (j <= textSize - patternSize)
		{
			result.iterationsTaken++;

			i = MAX(ell, memory) + 1;
			while (i < patternSize && pattern[i] == text[i + j])
				++i;
			if (i >= patternSize)
			{
				i = ell;
				while (i > memory && pattern[i] == text[i + j])
					--i;
				if (i <= memory)
				{
					result.positionsFound.push_back(j);
					if (Config::getInstance()->getFindOneOccurence())
					{
						return result;
					}
				}
				j += per;
				memory = patternSize - per - 1;
			}
			else
			{
				j += (i - ell);
				memory = -1;
			}
		}
	}
	else
	{
		per = MAX(ell + 1, patternSize - ell - 1) + 1;
		j = 0;
		while (j <= textSize - patternSize)
		{
			result.iterationsTaken++;

			i = ell + 1;
			while (i < patternSize && pattern[i] == text[i + j])
				++i;
			if (i >= patternSize)
			{
				i = ell;
				while (i >= 0 && pattern[i] == text[i + j])
					--i;
				if (i < 0)
				{
					result.positionsFound.push_back(j);
					if (Config::getInstance()->getFindOneOccurence())
					{
						return result;
					}
				}
				j += per;
			}
			else
				j += (i - ell);
		}
	}

	return result;
}
